package practise.alogrithm.hundredInterviewQuestions.secondTime;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * Created by Richard on 7/26/2014.
 */
public class FindTwoNumberJustAppearOnce {
    public List<Integer> find(List<Integer> array){
        int value =array.get(0);
        int flag=1;
        List<Integer> flagZero = new ArrayList<>(), flagOne= new ArrayList<>(),result= new ArrayList<>();
        for(int index=1; index<array.size();index++){
            value^=array.get(index);
        }
        while((value&flag)==0){
            flag = flag<<1;
        }
        for(int index=0;index<array.size();index++){
            if((array.get(index)&flag)==0){
                flagZero.add(array.get(index));
            }
            else {
                flagOne.add(array.get(index));
            }
        }
        value = flagZero.get(0);
        for(int index=1; index<flagZero.size();index++){
            value^=flagZero.get(index);
        }
        result.add(value);
        value = flagOne.get(0);
        for(int index=1; index<flagOne.size();index++){
            value^=flagOne.get(index);
        }
        result.add(value);
        return result;
    }

    public static  void  main(String[] args){
        System.out.print(new FindTwoNumberJustAppearOnce().find(new ArrayList<Integer>(Arrays.asList(new Integer[]{1,2,2,3,3,4,4,5,6,6}))));
    }
}
